package com.future;

import com.future.util.TreeNode;

import java.util.HashSet;
import java.util.Set;

/**
 * Description: 653. 两数之和 IV - 输入二叉搜索树
 *
 * @author weiruibai.vendor
 * Date: 2022/12/29 10:09
 */
public class Solution_653 {

    private static Solution_653 instance = new Solution_653();

    public static void main(String[] args) {
        // 5,3,6,2,4,null,7
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);

        root.right = new TreeNode(6);
        root.right.right = new TreeNode(7);
        int k = 9;
        System.out.println(instance.findTarget(root, 28));
    }

    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return calc(root, set, k);
    }

    private boolean calc(TreeNode root, Set<Integer> set, int k) {
        if (root == null) {
            return false;
        }
        int val = root.val;
        for (Integer num : set) {
            if (num + val == k) {
                return true;
            }
        }
        set.add(val);
        if (calc(root.left, set, k) || calc(root.right, set, k)) {
            return true;
        }
        return false;
    }
}
